package ljl.codetop300;

import java.util.ArrayList;
import java.util.List;

/**
 * 可真"简单"
 */
public class _offer_62_last_remaining {


  /**
   * 这波叫模拟，有个高手说 arrayList 不会超时，linkedList 会
   */
  static class simulate {
    public int lastRemaining(int n, int m) {
      List<Integer> list = new ArrayList<>();
      for (int i = 0; i < n; i++) {
        list.add(i);
      }
      int idx = 0;
      while (n > 1) {
        idx = (idx + m - 1) % n;
        list.remove(idx);
        n--;
      }
      return list.get(0);
    }
  }

  /**
   * 第一轮，删的是：(m-1)%n，下一轮第一个数字是：m%n，往后数 m-1 个删除，剩下谁：(2m)%(n-1)
   * 0    m%n
   * 1    m%n + 1
   * n-2  m%n + n-2
   * f(n) = (f(n-1) + m%n)%n = (f(n-1) + m)%n
   * 我只能帮到这了，再深究我就 hold 不住了
   */
  static class math {
    public int lastRemaining(int n, int m) {
      int x = 0;
      for (int i = 2; i <= n; i++) {
        x = (x + m) % i;
      }
      return x;
    }
  }
}
